// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-22 17:08
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.PathwithMaximumGold;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PathWithMaximumGold {
    int[][] gPoint; // 记录已经进入的矿点，进入并且开采过的矿点用1表示，没有进入的用0表示
    int gold = 0; // 当前开采的黄金量
    // 使用连个数组存储地图中可以勘测的四个方向，使用0,1,2,3可以映射到上下左右四个方向
    int[] xAxial = {0, 0, -1, +1};
    int[] yAxial = {+1, -1, 0, 0};
    List<Integer> path = new ArrayList<>();


    public int getMaximumGold(int[][] grid) {
        // 给定黄金地图中0单元格无法进入，当矿工无法移动的时候则结束采矿
        // 矿工勘探的时候面临方向选择
        // 图的遍历->需要记录被访问过的地点->确定所有可能都遍历过
        // 图的深度遍历DFS ？回溯算法->退回到转折点的时候需要恢复当时的黄金值
        // 节点访问记录 初始为0走过之后为1
        gPoint = new int[grid.length][grid[0].length];
        init(gPoint);
        // 确定几个点可以进行开采，然后对这些需要开采的点进行路线勘测
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (gPoint[i][j] == 0 && grid[i][j] != 0) {// 当前矿点没有被开采，并且存有金矿，则可以进入并开采
                    gPoint[i][j] = 1;
                    path.add(grid[i][j]);
                    travelMesh(grid, i, j, 0);
                    path.remove(path.size() - 1);
                    gPoint[i][j] = 0;
                }
            }
        }
        return gold;
    }

    private void init(int[][] gPoint) {
        for (int[] ints : gPoint) {
            Arrays.fill(ints, 0);
        }
    }

    /**
     * 矿工开采黄金路线,表格中数据为0的地方无法进入
     *
     * @param grid 黄金存储表格
     */
    // 方法获取访问中最大的gold全局变量
    public void travelMesh(int[][] grid, int x, int y, int tmpGold) {
        // 对上、下、左、右四个方向进行勘测，如果可以则直接开采
        tmpGold += grid[x][y];
        gold = Math.max(tmpGold, gold);
        for (int i = 3; i >= 0; i--) {
            int xm = x + xAxial[i];
            int ym = y + yAxial[i];
            // 勘测地点不能超出地图范围
            if (0 <= xm && xm < grid.length && 0 <= ym && ym < grid[0].length && gPoint[xm][ym] == 0 && grid[xm][ym] != 0) {
                // 当前方向上的矿点可以进行开采则直接进行开采
                gPoint[xm][ym] = 1; // 对开采过的矿点进行标记
                path.add(grid[xm][ym]);
                travelMesh(grid, xm, ym, tmpGold);
                path.remove(path.size() - 1);
                gPoint[xm][ym] = 0;   // 使用回溯算法抹除脚印避免干扰后面的遍历
            }
        }
        System.out.println("----------------");
        path.forEach(a -> System.out.print(a + "->" + "\t"));
//        System.out.println("total:" + gold);
        System.out.println();
    }


}
